package leetcode.code0668;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int m, n;

	public int findKthNumber(int m, int n, int k) {
		int ans = 0;
		int l = 1, r = m * n;
		this.m = m;
		this.n = n;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			int num = this.count(m, 1, mid);
			if (num >= k) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	private int count(int x, int y, int ans) {
		if (x == 0 || y == n + 1) {
			return 0;
		}
		int cur = 0;
		int xy = x * y;
		if (ans >= xy) {
			cur += x + this.count(x, y + 1, ans);
		} else {
			cur += this.count(x - 1, y, ans);
		}
		return cur;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(106, this.findKthNumber(10, 100, 301));
		HelpDebug.compare(3, this.findKthNumber(3, 3, 5));
		HelpDebug.compare(12, this.findKthNumber(10, 10, 30));
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int[][] ans = new int[10][10];
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				ans[i][j] = (i + 1) * (j + 1);
			}
		}
		HelpDebug.print(ans);
	}

}
